/**
 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

 你可以按 任何顺序 返回答案。



 示例 1：


 输入：n = 4, k = 2
 输出：
 [
 [2,4],
 [3,4],
 [2,3],
 [1,2],
 [1,3],
 [1,4],
 ]

 示例 2：


 输入：n = 1, k = 1
 输出：[[1]]



 提示：


 1 <= n <= 20
 1 <= k <= n

 Related Topics 数组 回溯 👍 820 👎 0

 */

package medium._0077.pck.s1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Combinations{
    public static void main(String[] args) {
        Solution solution = new Combinations().new Solution();
        final List<List<Integer>> combine = solution.combine(4, 2);
        System.out.println("combine = " + combine);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<>();
            Deque<Integer> path = new ArrayDeque<>();
            backTrace(1, n, k, path, res);
            return res;
        }

        /**
         * 回溯算法逻辑：每层回溯，决定取或者不去，直到取到足够的元素
         * @param begin 递归层数
         * @param n 最大数
         * @param k 组合的数据
         * @param path 选取的数据
         * @param res 最终汇总的结果
         */
        private void backTrace(int begin, int n, int k, Deque<Integer> path, List<List<Integer>> res) {
            if(k == 0) {
                res.add(new ArrayList<>(path));
                return;
            }
            if(begin == +1) {
                return;
            }
            //不选
            backTrace(begin+1, n, k, path,res);
            System.out.println();
            path.addLast(begin);
            //选择
            backTrace(begin+1, n, k-1,path, res);
            path.removeLast();

        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}